#include <iostream>
#include <vector>
#include <time.h>

namespace ns_skiplist
{
    struct SkipListNode
    {
        int _val;
        std::vector<SkipListNode *> _nextV;
        SkipListNode(int val, int level)
            : _val(val), _nextV(level, nullptr)
        {
        }
    };

    class SkipList
    {
        typedef SkipListNode Node;

    public:
        SkipList()
        {
            srand(time(nullptr));
            _head = new Node(-1, 1);
        }

    private:
        size_t randomLevel()
        {
            size_t level = 1;
            while (rand() <= RAND_MAX * _p && level < _maxLevel)
            {
                level++;
            }
            return level;
        }
        std::vector<Node *> findNodePrev(int num)
        {
            Node *cur = _head;
            int level = _head->_nextV.size() - 1;
            std::vector<Node *> prevV;
            while (level >= 0)
            {
                if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
                {
                    cur = cur->_nextV[level];
                }
                else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val >= num)
                {
                    prevV[level] = cur;
                    level--;
                }
            }
            return prevV;
        }

    public:
        bool search(int target)
        {
            Node *cur = _head;
            int level = _head->_nextV.size() - 1;
            while (level >= 0)
            {
                if (cur->_nextV[level] && cur->_nextV[level]->_val < target)
                {
                    cur = cur->_nextV[level];
                }
                else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target)
                {
                    level--;
                }
                else
                {
                    return true;
                }
            }
            return false;
        }
        void add(int num)
        {
            std::vector<Node *> prevV = findNodePrev(num);
            size_t n = randomLevel();
            Node *newnode = new Node(num, n);
            if (n > _head->_nextV.size())
            {
                _head->_nextV.resize(n, nullptr);
                prevV.resize(n, _head);
            }
            for (size_t i = 0; i < n; i++)
            {
                newnode->_nextV[i] = prevV[i]->_nextV[i];
                prevV[i]->_nextV[i] = newnode;
            }
        }
        bool erase(int num)
        {
            std::vector<Node *> prevV = findNodePrev(num);
            if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)
            {
                return false;
            }
            else
            {
                Node *del = prevV[0]->_nextV[0];
                for (size_t i = 0; i < del->_nextV.size(); i++)
                {
                    prevV[i]->_nextV[i] = del->_nextV[i];
                }
                delete del;
            }
        }

    private:
        Node *_head;
        size_t _maxLevel = 32;
        double _p = 0.5;
    };
} // namespace ns_skiplist
